/*================================================================
*   文件名称：main.cpp
*   创 建 者：yang qiang
*   创建日期：2020年03月11日
*   版    本：v1.0.0
*   描    述：
*   Copyright (C) 2020 All rights reserved.
*   
* ================================================================*/


#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    /**
     * @param n: An integer
     * @param nums: An array
     * @return: the Kth largest element
     */
    int kthLargestElement(int n, vector<int> &nums) {
        return helper(nums, nums.size()-n+1, 0, nums.size()-1);
    }

    int helper(vector<int> &nums, int n, int left, int right){
        int pos = partition(nums, left, right);
        if(pos + 1 == n){
            return nums[pos];
        }else if(pos + 1 < n){
            return helper(nums, n, pos+1, right);
        }else{
            return helper(nums, n, left, pos-1);
        }
    }

    int partition(vector<int>& nums, int left, int right){
        if(left == right){
            return left;
        }

        int key = nums[left];
        while(left < right){
            while(left < right && nums[right] >= key){
                right--;
            }
            nums[left] = nums[right];

            while(left < right && nums[left] <= key){
                left++;
            }
            nums[right] = nums[left];
        }

        nums[left] = key;

        return left;
    }
};